package leetcode.code0115;

public class Solution extends Solution115 {

	@Override
	public int numDistinct(String s, String t) {
//		if (t == null || t.length() == 0)
//			return 1;
//		if (s == null || s.length() == 0)
//			return 0;
		int lens = s.length();
		int lent = t.length();
		char[] cs = s.toCharArray();
		char[] ct = t.toCharArray();
		int[][] dp = new int[lent + 1][lens + 1];//dp[x][y] t[0..x] s[0..y]子序列个数
//		dp[0][0] = 1;
//		for (int i = 1; i <= lent; i++) {
//			dp[i][0] = 0;
//		}
//		for (int j = 1; j <= lens; j++) {
//			dp[0][j] = 1;
//		}
		for (int j = 0; j <= lens; j++) {
			dp[0][j] = 1;
		}
		for (int i = 1; i <= lent; i++) {
			for (int j = i; j <= lens; j++) {
				dp[i][j] = ct[i - 1] == cs[j - 1] ? dp[i - 1][j - 1] + dp[i][j - 1] : dp[i][j - 1];
			}
		}
		return dp[lent][lens];
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();

	}

}
